class Solution {//leetcode375——猜数字大小
private:
    int dfs(int begin,int end){
        if(begin>=end) return 0;
        if(memory[begin][end]!=-1) return memory[begin][end];
        int ret=INT_MAX;
        for(int i=begin;i<=end;i++){
            int left_val=dfs(begin,i-1);
            int right_val=dfs(i+1,end);
            ret=min(ret,(max(left_val,right_val)+i));
        }
        memory[begin][end]= ret;
        return memory[begin][end];
    }
public:
    int getMoneyAmount(int n) {
        memory.resize(n+1,vector<int>(n+1,-1));
        int ret=0;
        return dfs(1,n);
    }
private:
    vector<vector<int>> memory;
};